package com.bitauto.i.commonUtils.leet;

/**
 * 利用链表计算两个超大的数
 * 时间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的长度。
 * 空间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的长度。而其实新的 List 最大长度是 O（max（m，n））+ 1，因为我们的 head 没有存储值。
 */
public class Answer2 {

    public static void main(String[] args) {
        Node l1 = new Node(3);
        Node l11= new Node(8);
        Node l12= new Node(2);
        l11.setNext(l12);
        l1.setNext(l11);

        Node l2 = new Node(2);
        Node l21 = new Node(9);
        Node l22 = new Node(5);
        l21.setNext(l22);
        l2.setNext(l21);

        Node result=calculate(l1,l2);
        Node p=reverseList(result);
        while (p!=null){
            System.out.println(p.getValue());
            p=p.next;
        }
    }

    public static Node reverseList(Node head){
        if(head==null){
            return null;
        }
        Node pre=null;
        Node next;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

    private static Node calculate(Node l1, Node l2) {
        //结果头
        Node result = new Node(0);
        //链表的头，也就是个位
        Node p=l1;
        Node q=l2;
        //结果列表计算位
        Node curr = result;
        //进位
        int carry = 0;

        while(p!=null || q!=null){
            int x = p!=null?p.getValue():0;
            int y = q!=null?q.getValue():0;

            int sum=x+y+carry;
            //利用除10看是否需要进位
            carry=sum/10;
            //所在位剩余的数
            curr.next=new Node(sum%10);
            curr=curr.next;
            if (p!=null){
                p=p.next;
            }
            if (q!=null){
                q=q.next;
            }
        }
        if(carry>0){
            curr.next = new Node(carry);
        }
        //以为开头是个0，所以返回它的下一位
        return result.next;
    }

    static class Node{
        private Integer value;
        private Node next;
        Node(int x){
            value = x;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }



}
